/*
题目: 绝对差不超过限制的最长连续子数组
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
 */
public class LongestSubarray {
    // 单调队列
    public int longestSubarray(int[] nums, int limit) {
        // 维持 区间 的最大值 和 最小值
        Deque<Integer> minQue = new LinkedList<> ();
        Deque<Integer> maxQue = new LinkedList<> ();
        int left = 0, n = nums.length;;

        int src = 0;
        for (int i = 0; i < n; i ++) {
            // 队头是最小值, 递增
            // 以下布尔表达式不能取等号, 不能提前将相等元素提前排出
            while (!minQue.isEmpty() && minQue.peekLast() > nums[i]) {
                minQue.pollLast();
            }
            minQue.offerLast(nums[i]);

            // 队头是最大值, 递减
            while (!maxQue.isEmpty() && maxQue.peekLast() < nums[i]) {
                maxQue.pollLast();
            }
            maxQue.offerLast(nums[i]);

            // 维持满足题意的 窗口内的长度
            while (!maxQue.isEmpty() && !minQue.isEmpty() && maxQue.peekFirst() - minQue.peekFirst() > limit) {
                if (maxQue.peekFirst() == nums[left]) {
                    maxQue.pollFirst();
                }
                if (minQue.peekFirst() == nums[left]) {
                    minQue.pollFirst();
                }
                left ++;
            }
            src = Math.max(src, i - left + 1);
        }

        return src;
    }

    // TreeMap  ---------------------------------------------------------------------------------------------------
    public int longestSubarray1(int[] nums, int limit) {
        // 维持 窗口中的 最大值和最小值
        TreeMap<Integer, Integer> map = new TreeMap<> ();
        int left = 0, n = nums.length;

        int src = 0;
        for (int i = 0; i < n; i ++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);

            while (!map.isEmpty() && map.lastKey() - map.firstKey() > limit) {
                int t = map.get(nums[left]);
                if (t == 1)     map.remove(nums[left]);
                else            map.put(nums[left], t - 1);
                left ++;
            }
            src = Math.max(src, i - left + 1);
        }

        return src;
    }
}
